Palindrome removal

Time: O(N^3); Space: O(N^2); hard

Given an integer array arr, in one move you can select a palindromic subarray arr[i], arr[i+1], …, arr[j] where i <= j, and remove that subarray from the given array.

Note that after removing a subarray, the elements on the left and on the right of that subarray move to fill the gap left by the removal.

Return the minimum number of moves needed to remove all numbers from the array.

Example 1:

Input: arr = [1,2]

Output: 2

Example 2:

Input: arr = [1,3,4,1,5]

Output: 3

Explanation:

• Remove [4] then remove [1,3,1] then remove [5].

Constraints:

• 1 <= len(arr) <= 100

• 1 <= arr[i] <= 20

Hints:

1. DP pattern: dp[i][j] = min(dp[i][j], dp[i][k-1] + dp[k+1][j]), where arr[k]==arr[i]

1. Dynamic programming [O(N^3), O(N^2)]

class Solution1(object):
    """
    Time: O(N^3)
    Space: O(N^2)
    """
    def minimumMoves(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        dp = [[0 for _ in range(len(arr)+1)] for _ in range(len(arr)+1)]

        for l in range(1, len(arr)+1):
            for i in range(len(arr)-l+1):
                j = i+l-1
                if l == 1:
                    dp[i][j] = 1
                else:
                    dp[i][j] = 1+dp[i+1][j]
                    if arr[i] == arr[i+1]:
                        dp[i][j] = min(dp[i][j], 1+dp[i+2][j])
                    for k in range(i+2, j+1):
                        if arr[i] == arr[k]:
                            dp[i][j] = min(dp[i][j], dp[i+1][k-1] + dp[k+1][j])

        return dp[0][len(arr)-1]

s = Solution1()

arr = [1,2]
assert s.minimumMoves(arr) == 2

arr = [1,3,4,1,5]
assert s.minimumMoves(arr) == 3

2. Dynamic programming (Bottom-up)

class Solution2(object):
    def minimumMoves(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        n = len(arr)
        dp = [[100] * n for _ in range(n)]

        for i in range(n-1, -1, -1):
            dp[i][i] = 1
            for j in range(i+1, n):
                if j == n:
                    break
                dp[i][j] = 1 + (dp[i+1][j] if i+1<n else 0)
                for k in range(i+1, j+1):
                    if arr[i] == arr[k]:
                        if k == i + 1:
                            dp[i][j] = min(dp[i][j], 1 + (dp[k+1][j] if k+1<=j else 0))
                        else:
                            dp[i][j] = min(dp[i][j], dp[i+1][k-1] + (dp[k+1][j] if k+1<=j else 0))
        return dp[0][n-1]

s = Solution2()

arr = [1,2]
assert s.minimumMoves(arr) == 2

arr = [1,3,4,1,5]
assert s.minimumMoves(arr) == 3

3. DFS

import collections

class Solution3(object):
    def minimumMoves(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        memo = {}
        d = collections.defaultdict(list)
        for i,c in enumerate(arr):
            d[c].append(i)

        def dp(i,j):
            if i == j:
                return 1
            if i > j:
                return 0
            if (i,j) not in memo:
                res = 1 + dp(i+1, j)
                for k in d[arr[i]]:
                    if k == i + 1:
                        res = min(res, 1 + dp(k+1, j))
                    elif i + 1 < k <= j:
                        res = min(res, dp(i+1, k-1) + dp(k+1, j))
                memo[i,j] = res
            return memo[i,j]

        return dp(0, len(arr)-1)

s = Solution3()

arr = [1,2]
assert s.minimumMoves(arr) == 2

arr = [1,3,4,1,5]
assert s.minimumMoves(arr) == 3

See also:

https://leetcode.com/problems/palindrome-removal